package mybtree;

import com.sun.org.apache.bcel.internal.generic.BREAKPOINT;
import rbtree.RBTree;

public class MyBtree {

    static class BTRNode {
        public int[] keys;//关键字
        public BTRNode[] subs;//孩子
        public BTRNode parent;//当前孩子节点的父亲结点
        public int usedSize;//当前结点关键字的数量

        public BTRNode() {
            //这里多给一个空间，是为了更好的分裂
            this.keys =  new int[M];
            this.subs = new BTRNode[M + 1];
        }
    }

    public static final int M = 3;
    public BTRNode root;//当前B树的根节点

    /**
     * 插入元素
     * @param key
     */
    public boolean insert(int key) {
        if(root == null) {
            root = new BTRNode();
            root.keys[0] = key;
            root.usedSize++;
            return true;
        }
        //2. 当树不为空，就看Key是否存在B树中
        Pair<BTRNode, Integer> pair = find(key);
        //根据判断这里的val值是否为-1， 确定是否存在key
        if(pair.getVal() != -1) {//结点存在
            return false;
        }
        //不存在key，就要进行插入(插入排序)
        BTRNode parent = pair.getKey();
        int index = parent.usedSize - 1;
        for(; index >= 0; index--) {
            if(parent.keys[index] >= key) {
                parent.keys[index + 1] = parent.keys[index];
            } else {
                break;
            }
        }
        parent.keys[index + 1] = key;
        parent.usedSize++;
        //为什么不处理孩子？
        //因为每次插入都是在叶子结点，所以叶子结点都是null
        if(parent.usedSize < M) {
            //没有满
            return true;
        } else {
            //满了，需要分裂
            split(parent);
            return true;
        }
    }

    /**
     * 分裂逻辑
     * @param cur 代表当前需要分裂的结点
     */
    private void split(BTRNode cur) {
        BTRNode newNode = new BTRNode();
        //1.先存储当前需要分裂结点的父节点
        BTRNode parent = cur.parent;
        //2.开始挪动数据
        int mid = cur.usedSize >> 1;
        int i = mid + 1;
        int j = 0;
        for(; i < cur.usedSize; i++) {
            //这里既要拷贝数值也需要拷贝孩子的地址
            newNode.keys[j] = cur.keys[i];
            newNode.subs[j] = cur.subs[i];
            //处理刚刚拷贝过来的孩子节点的父亲结点，为新分裂的结点
            if(newNode.subs[j] != null){
                newNode.subs[j].parent = newNode;
            }
            j++;
        }
        //多拷贝一次孩子
        newNode.subs[j] = cur.subs[i];
        if(newNode.subs[j] != null){
            newNode.subs[j].parent = newNode;
        }
        //更新当前新节点的有效数据
        newNode.usedSize = j;
        //这里-1是因为将来要提到父亲结点的key
        cur.usedSize = cur.usedSize - j - 1;

        //处理根节点的情况
        if(cur == root) {
            root = new BTRNode();
            root.keys[0] = cur.keys[mid];
            root.subs[0] = cur;
            root.subs[1] = newNode;
            root.usedSize = 1;
            cur.parent = root;
            newNode.parent = root;
            return;
        }

        //让新的结点的父亲指向刚刚分裂结点的父亲
        newNode.parent = parent;

        //开始移动父亲结点
        int endT = parent.usedSize - 1;
        int midVal = cur.keys[mid];
        for(; endT >= 0; endT--) {
            if(parent.keys[endT] >= midVal) {
                parent.keys[endT + 1] = parent.keys[endT];
                parent.subs[endT + 2] = parent.subs[endT + 1];
            } else {
                break;
            }
        }
        parent.keys[endT + 1] = midVal;
        //将当前父亲结点的孩子结点新增为newNode;
        parent.subs[endT + 2] = newNode;
        parent.usedSize++;
        if(parent.usedSize >= M) {
            split(parent);
        }
    }

    /**
     * 返回一个值是否可行？
     * 地址-》无法记录你存储在哪
     * 所以需要返回一对
     * @param key
     * @return
     */
    private Pair<BTRNode, Integer> find(int key) {
        BTRNode cur = root;
        BTRNode parent = null;
        while(cur != null) {
            int i = 0;
            while(i < cur.usedSize) {
                if(cur.keys[i] == key) {
                    //返回一个当前找到的结点 和 当前结点的下标
                    return new Pair<>(cur, i);
                } else if(cur.keys[i] < key) {
                    i++;
                } else {
                    break;
                }
            }
            parent = cur;
            cur = cur.subs[i];
        }
        return new Pair<>(parent, -1);
    }

    //测试
    public static void main(String[] args) {
        MyBtree myBtree = new MyBtree();
        int[] arr = {53, 139, 75, 49, 145, 36, 101};
        for(int i = 0; i < arr.length; i++) {
            myBtree.insert(arr[i]);
        }
        System.out.println("123121");
    }
}
